package J4_7;

import java.util.HashMap;
import java.util.Map;

public class test {
    //你是一个专业的小偷，计划偷窃沿街的房屋，
    // 每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，
    // 这意味着第一个房屋和最后一个房屋是紧挨着的。
    // 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
    //
    //给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return nums[0];
        } else if (n == 2) {
            return Math.max(nums[0], nums[1]);
        } else {
            return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
        }
    }

    public int robRange(int[] nums, int index1, int index2) {
        int n = nums.length;
        if (n == 0) return 0;
        int[] f = new int[n];
        int[] g = new int[n];
        f[index1] = nums[index1];
        g[0] = 0;
        for (int i = index1 + 1; i <= index2; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(g[i - 1], f[i - 1]);
        }
        return Math.max(g[index2], f[index2]);
    }


    //给你一个整数数组 nums ，你可以对它进行一些操作。
    //
    //每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
    //
    //开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
    public int deleteAndEarn(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + i);
        }
        int[] f = new int[10001];
        int[] g = new int[10001];
        f[1] = map.getOrDefault(1, 0);
        g[1] = 0;
        for (int i = 2; i < 10001; i++) {
            f[i] = g[i - 1] + map.getOrDefault(i, 0);
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[10000], g[10000]);
    }


    //假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
    //
    //当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
    //
    //例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
    //
    //请计算出粉刷完所有房子最少的花费成本。
    public int minCost(int[][] costs) {
        int n = costs.length;
        int[][] dp = new int[n + 1][3];
        for (int i = 1; i <= n; i++) {
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][0]) + costs[i - 1][2];
        }
        return Math.min(Math.min(dp[n][0], dp[n][1]), dp[n][2]);
    }


    //给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​
    //
    //设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
    //
    //卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
    //注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][3];
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; i++) {
            //买入状态
            dp[i][0] = Math.max(dp[i - 1][2] - prices[i], dp[i - 1][0]);
            //冷冻期状态
            dp[i][1] = dp[i - 1][0] + prices[i];
            //可交易状态
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1]);
        }
        return Math.max(dp[n - 1][1], dp[n - 1][2]);
    }


    //给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
    //
    //你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
    //
    //返回获得利润的最大值。
    //
    //注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        return dp[n - 1][1];

    }

    //给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
    //
    //设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
    //
    //注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
    public int maxProfit1(int[] prices) {
        int n = prices.length;
        int[][][] dp = new int[n][2][3];
        for (int i = 0; i < 3; i++) {
            dp[0][0][i] = dp[0][1][i] = -0x3f3f3f3f;
        }
        dp[0][0][0] = -prices[0];
        dp[0][1][0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                dp[i][0][j] = Math.max(dp[i - 1][0][j], dp[i - 1][1][j] - prices[i]);
                dp[i][1][j] = dp[i - 1][1][j];
                if (j > 0) {
                    dp[i][1][j] = Math.max(dp[i - 1][1][j], dp[i - 1][0][j - 1] + prices[i]);
                }
            }
        }
        return Math.max(Math.max(dp[n - 1][1][0], dp[n - 1][1][1]), dp[n - 1][1][2]);
    }

    //给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，
    // 然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
    //
    //如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
    public int minOperations(int[] nums, int x) {
        int sum = 0, n = nums.length;
        for (int i : nums) {
            sum += i;
        }
        int target = sum - x;
        if (target < 0) {
            return -1;
        }
        int l = 0, r = 0, sum1 = 0, ret = -1;
        while (r < n) {
            sum1 += nums[r];
            while (sum1 > target) {
                sum1 -= nums[l++];
            }
            if (sum1 == target) {
                ret = Math.max(ret, r - l + 1);
            }
            r++;
        }
        if (ret == -1) {
            return -1;
        }
        return n - ret;
    }
}
